package com.mdnote.practice.dp;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/18
 * @description  不同路径
 */
public class LeetCode62 {


    public static void main(String[] args) {
        LeetCode62 leetCode62 = new LeetCode62();
        int res = leetCode62.uniquePaths(3, 2);
        System.out.println(res);
    }
    public int uniquePaths(int m, int n) {
        // recursion
        int[][] board = new int[m][n];
//        int count = recursion(0, 0, board);

        // dp
//        int count = dp(board);

        // dp plus
        int count = dpPlus(m, n);
        return count;
    }

    private int dpPlus(int m, int n) {

        int[] preRow = new int[n];
        Arrays.fill(preRow, 1);
        for (int i = m - 2; i >= 0; i--) {
            preRow[preRow.length - 1] = 1;
            for (int j = n -2; j >= 0; j--) {
                preRow[j] = preRow[j] + preRow[j + 1];

            }
        }
        return preRow[0];
    }

    private int dp(int[][] board) {

        // a初始化，我们从最下面开始探测
        for (int i = 0; i < board.length; i++) {
            board[i][board[i].length - 1] = 1;
        }
        Arrays.fill(board[board.length - 1], 1);

        // 从右下角开始网上计算最优质
        for (int i = board.length - 2; i >= 0; i--) {
            for (int j = board[i].length - 2; j >= 0; j--) {
                board[i][j] = board[i + 1][j] + board[i][j + 1];
            }
        }
        return board[0][0];
    }

    private int recursion(int row, int column, int[][] board) {
        if (row == board.length || column == board[0].length) {
            return 0;
        }
        // Terminator
        if (row + 1 == board.length && column + 1 == board[0].length) {
            board[row][column] = 1;
            return 1;
        }
        // Process current logic
        // drill down
        if (board[row][column] == 0) {
            board[row][column] = recursion(row + 1, column, board) + recursion(row, column + 1, board);
        }
        // restore current data
        return board[row][column];
    }


}
